package array.findKthLargest;

import java.util.Random;

/**
 * @Date 2020/04/10
 * @author 王光浩
 * @Thinking 简化之后的快速排序，减而治之。
 * @Analysis 时间复杂度O（n）——最好，最差O（nlogn），空间复杂度O（n）
 */
public class MyMethodTwo {
	private int ret;
	public int findKthLargest(int[] nums, int k) {
		helper(0,nums.length-1,nums,nums.length-k);
		return ret;
	}
	private void helper(int left,int right,int nums[],int target) {
		 if(left==right) {
			 ret=nums[left];
			 return;
		 }
		 int l=left;
		 int r=right;
		 Random random=new Random();  //使用随机数来代替l，当序列为近乎有序的时候可以防止时间复杂度退化到O（n^2）
		 int index=left+random.nextInt(right-left);
		 int tem=nums[index];
		 nums[index]=tem;
		 nums[l]=tem;
		 while(l<r) {
			 while(r>l && nums[r]>=tem)r--;
			 nums[l]=nums[r];
			 while(r>l && nums[l]<tem)l++;
			 nums[r]=nums[l];
		 }
		 nums[l]=tem;
		 if(l==target) {
			 ret=nums[l];
			 return;
		 }
		 else if(l>target) helper(left,l-1,nums,target);
		 else helper(l+1,right,nums,target);
	}
}
